package com.caoyanan.algorithm.question.zuoTraining.training004.class02;

import com.caoyanan.algorithm.question.zuoTraining.LogarithmInputGenerator;

import java.util.Arrays;

/**
 * 不排序求最大相邻差
 *
 * 给定一个无序数组arr，返回如果排序之后，相邻数之间的最大差值
 * {3,1,7,9}，如果排序后{1,3,7,9}，相邻数之间的最大差值来自3和7，返回4
 * 要求：不能真的进行排序，并且要求在时间复杂度O(N)内解决
 * @author: caoyanan
 * @time: 2021/6/4 6:09 下午
 */
public class Question03_NotSortFindMaxNeighbor {

    public static void main(String[] args) {

        int count = 10000;
        for (int i = 0; i < count; i++) {
            int[] arr = LogarithmInputGenerator.getInstance().generateRandomArray(10, 100);
            int answer = noSortFindMaxNeighbor(arr);
            int toCompared = sortFindMaxNeighbor(arr);
            if (answer != toCompared) {
                System.out.printf("数组: %s 不排序最大相邻数: %s, 排序最大相邻数 %s \n",
                        Arrays.toString(arr), answer, toCompared);
            }
        }
    }

    /**
     * 比较器
     * @param arr
     * @return
     */
    private static int sortFindMaxNeighbor(int[] arr) {
        Arrays.sort(arr);
        int answer = arr[1] - arr[0];

        for (int i = 2; i < arr.length; i++) {
            answer = Math.max(answer, arr[i] - arr[i - 1]);
        }
        return answer;
    }

    /**
     * 不排序得到数组 排序后相邻数 之间的最大值
     * 利用桶的思想，首先，找到数组中的最大值max和min，假设数组的长度是n
     * 然后准备n+1个桶，将数组里面的树往这些桶里面放，min一定会放到最左边的桶，max一定会放到最右边的桶，
     * 然后中间的数分别按照 桶范围哈希 依次放入对应范围大小桶。(int) ((num - min) * len / (max - min))
     * 都放完之后，相邻数的差值一种情况是桶内相邻数的差值，一种是相邻通之间的差值，
     * 因为有一个空桶的存在，所以，相邻通的差值一定会大于桶内的差值
     * 注意，答案不一定就是那个空桶前后两桶相邻数的差值，
     *      比如[0, 15, 21, 39, 51, 61, 71, 85, 100],准备了10个桶 ，
     *      0~10(0), 11~20(15), 21~30(21), 31~40(39), 41~50(空桶), 51~60(51), 61~70(61), 71~80(71), 81~90(85), 91~100(100)
     *      空桶两边的 51 - 39 = 12.  而2桶和3桶的相邻差 39 - 21 = 18
     * 记录每个桶的最小值和最大值，然后每两个桶之间相邻差值进行比较，求出最大值
     *
     * 那搞空桶的目的是什么？搞一个不算差的平凡解，它的目的不是搞出答案，它的目的是杀死比平凡解还要差的一个解，就是桶内部的差值这种情况。
     * @param arr
     * @return
     */
    private static int noSortFindMaxNeighbor(int[] arr) {
        int min = Integer.MAX_VALUE;
        int max= Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            min = Math.min(arr[i], min);
            max = Math.max(arr[i], max);
        }

        // 准备桶，记录是否是空桶，桶内最大值，桶内最小值
        int n = arr.length + 1;
        boolean[] bucketExists = new boolean[n];
        int[] bucketMin = new int[n];
        int[] bucketMax = new int[n];

        for (int i = 0; i < arr.length; i++) {
            int hash = arr.length * (arr[i] - min) / (max - min);
            bucketMin[hash] = bucketExists[hash] ? Math.min(bucketMin[hash], arr[i]) : arr[i];
            bucketMax[hash] = bucketExists[hash] ? Math.max(bucketMax[hash], arr[i]) : arr[i];
            bucketExists[hash] = Boolean.TRUE;
        }

        // 两个桶之间的最大值
        int answer = Integer.MIN_VALUE;
        int lastExistsBucket = 0;
        for (int i = 1; i < n; i++) {
            if (bucketExists[i]) {
                answer = Math.max(answer, bucketMin[i] - bucketMax[lastExistsBucket]);
                lastExistsBucket = i;
            }
        }
        return answer;
    }
}
